{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Markov Decision Processes \n",
    "\n",
    "The Markov Decision Process (MDP) provides a mathematical framework for\n",
    "solving the RL problem. Almost all RL problems can be modeled as an MDP. MDPs\n",
    "are widely used for solving various optimization problems. In this section, we will\n",
    "understand what an MDP is and how it is used in RL.\n",
    "\n",
    "To understand an MDP, first, we need to learn about the Markov property and\n",
    "Markov chain.\n",
    "\n",
    "\n",
    "## Markov Property and Markov Chain \n",
    "\n",
    "The Markov property states that the future depends only on the present and not\n",
    "on the past. The Markov chain, also known as the Markov process, consists of a\n",
    "sequence of states that strictly obey the Markov property; that is, the Markov chain\n",
    "is the probabilistic model that solely depends on the current state to predict the next\n",
    "state and not the previous states, that is, the future is conditionally independent of\n",
    "the past.\n",
    "\n",
    "For example, if we want to predict the weather and we know that the current state is\n",
    "cloudy, we can predict that the next state could be rainy. We concluded that the next\n",
    "state is likely to be rainy only by considering the current state (cloudy) and not the\n",
    "previous states, which might have been sunny, windy, and so on.\n",
    "However, the Markov property does not hold for all processes. For instance,\n",
    "throwing a dice (the next state) has no dependency on the previous number that\n",
    "showed up on the dice (the current state).\n",
    "\n",
    "Moving from one state to another is called a transition, and its probability is called\n",
    "a transition probability. We denote the transition probability by $P(s'|s) $. It indicates\n",
    "the probability of moving from the state $s$ to the next state $s'$.\n",
    "\n",
    "Say we have three states (cloudy, rainy, and windy) in our Markov chain. Then we can represent the\n",
    "probability of transitioning from one state to another using a table called a Markov\n",
    "table, as shown in the following table:\n",
    "\n",
    "![title](Images/8.PNG)\n",
    "\n",
    "From the above table, we can observe that:\n",
    "\n",
    "* From the state cloudy, we transition to the state rainy with 70% probability and to the state windy with 30% probability.\n",
    "\n",
    "* From the state rainy, we transition to the same state rainy with 80% probability and to the state cloudy with 20% probability.\n",
    "\n",
    "* From the state windy, we transition to the state rainy with 100% probability.\n",
    "\n",
    "We can also represent this transition information of the Markov chain in the form of\n",
    "a state diagram, as shown below:\n",
    "\n",
    "\n",
    "![title](Images/9.png)\n",
    "We can also formulate the transition probabilities into a matrix called the transition\n",
    "matrix, as shown below:\n",
    "\n",
    "![title](Images/10.PNG)\n",
    "\n",
    "Thus, to conclude, we can say that the Markov chain or Markov process consists of a\n",
    "set of states along with their transition probabilities.\n",
    "\n",
    "## Markov Reward Process\n",
    "\n",
    "The Markov Reward Process (MRP) is an extension of the Markov chain with the\n",
    "reward function. That is, we learned that the Markov chain consists of states and a\n",
    "transition probability. The MRP consists of states, a transition probability, and also a\n",
    "reward function.\n",
    "\n",
    "A reward function tells us the reward we obtain in each state. For instance, based on\n",
    "our previous weather example, the reward function tells us the reward we obtain\n",
    "in the state cloudy, the reward we obtain in the state windy, and so on. The reward\n",
    "function is usually denoted by $R(s)$.\n",
    "\n",
    "Thus, the MRP consists of states $s$, a transition probability $P(s|s')$\n",
    "function $R(s)$. \n",
    "\n",
    "## Markov Decision Process\n",
    "\n",
    "The Markov Decision Process (MDP) is an extension of the MRP with actions. That\n",
    "is, we learned that the MRP consists of states, a transition probability, and a reward\n",
    "function. The MDP consists of states, a transition probability, a reward function,\n",
    "and also actions. We learned that the Markov property states that the next state is\n",
    "dependent only on the current state and is not based on the previous state. Is the\n",
    "Markov property applicable to the RL setting? Yes! In the RL environment, the agent\n",
    "makes decisions only based on the current state and not based on the past states. So,\n",
    "we can model an RL environment as an MDP.\n",
    "\n",
    "Let's understand this with an example. Given any environment, we can formulate\n",
    "the environment using an MDP. For instance, let's consider the same grid world\n",
    "environment we learned earlier. The following figure shows the grid world environment,\n",
    "and the goal of the agent is to reach state I from state A without visiting the shaded\n",
    "state\n",
    "\n",
    "\n",
    "![title](Images/11.png)\n",
    "\n",
    "An agent makes a decision (action) in the environment only based on the current\n",
    "state the agent is in and not based on the past state. So, we can formulate our\n",
    "environment as an MDP. We learned that the MDP consists of states, actions,\n",
    "transition probabilities, and a reward function. Now, let's learn how this relates to\n",
    "our RL environment:\n",
    "\n",
    "__States__ – A set of states present in the environment. Thus, in the grid world\n",
    "environment, we have states A to I.\n",
    "\n",
    "__Actions__ – A set of actions that our agent can perform in each state. An agent\n",
    "performs an action and moves from one state to another. Thus, in the grid world\n",
    "environment, the set of actions is up, down, left, and right.\n",
    "\n",
    "__Transition probability__ – The transition probability is denoted by $ P(s'|s,a) $. It\n",
    "implies the probability of moving from a state $s$ to the next state $s'$ while performing\n",
    "an action $a$. If you observe, in the MRP, the transition probability is just $ P(s'|s,a) $ that\n",
    "is, the probability of going from state $s$ to state $s'$ and it doesn't include actions. But in MDP we include the actions, thus the transition probability is denoted by $ P(s'|s,a) $. \n",
    "\n",
    "For example, in our grid world environment, say, the transition probability of moving from state A to state B while performing an action right is 100% then it can be expressed as: $P( B |A , \\text{right}) = 1.0 $. We can also view this in the state diagram as shown below:\n",
    "\n",
    "\n",
    "![title](Images/12.png)\n",
    "\n",
    "Suppose, our agent is in state C and the transition probability of moving from state C to the state F while performing an action down is 90% then it can be expressed as: $P( F |C , \\text{down}) = 0.9 $. We can also view this in the state diagram as shown below:\n",
    "\n",
    "\n",
    "![title](Images/13.png)\n",
    "\n",
    "__Reward function__ -  The reward function is denoted by $R(s,a,s') $. It implies the reward our agent obtains while transitioning from a state $s$ to the state $s'$ while performing an action $a$. \n",
    "\n",
    "Say, the reward we obtain while transitioning from the state A to the state B while performing an action right is -1, then it can be expressed as $R(A, \\text{right}, B) = -1 $. We can also view this in the state diagram as shown below:\n",
    "\n",
    "\n",
    "![title](Images/14.png)\n",
    "\n",
    "Suppose, our agent is in state C and say, the reward we obtain while transitioning from the state C to the state F while performing an action down is  +1, then it can be expressed as $R(C, \\text{down}, F) = +1 $. We can also view this in the state diagram as shown below:\n",
    "\n",
    "\n",
    "![title](Images/15.png)\n",
    "\n",
    "\n",
    "Thus, an RL environment can be represented as an MDP with states, actions,\n",
    "transition probability, and the reward function. But wait! What is the use of\n",
    "representing the RL environment using the MDP? We can solve the RL problem easily\n",
    "once we model our environment as the MDP. For instance, once we model our grid\n",
    "world environment using the MDP, then we can easily find how to reach the goal\n",
    "state I from state A without visiting the shaded states. We will learn more about this\n",
    "in the upcoming chapters. Next, we will go through more essential concepts of RL.\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
